The present invention is directed to image processing and particular to developing dither matrices for dispersed dither.
Image data are typically taken and stored in formats that are not well suited to use by image-presentation devices such as printers. A digitally stored or processed gray-scale image typically consists of a finely quantized--say, 8-bit--scalar pixel value associated with each a large number of picture elements ("pixels") of which the image consists. Digital color images are similar, except the pixel value is a vector rather than a scalar, and a similarly finely quantized value represents each of the vector's color components. So although the following discussion will be presented in terms of gray-scale images, it applies equally to a color image's individual color components.
Consider the case of an 8-bit-per-pixel digital image. A pixel can have any gray value between 0, for completely white, and 255 (=2.sup.8 -1), for completely black. Actually, the meaning in the stored image is often just the reverse--i.e., 0 represents completely black and 255 represents completely white. But when the imaging device is one like a printer, in which an increase in the applied amount of the imaging agent (ink in the case of a printer) results in a reduction in image brightness, the image data are usually converted to complementary values during the image-presentation process. The discussion that follows will be presented in terms of such complementary color values--i.e., a higher value will mean a darker image--but the principles apply equally to a positive-color presentation such as that which occurs in a cathode-ray tube.
In contrast to the original image's 256 possible values, the typical printer can render any single pixel only completely white or completely black (in gray-scale printing). Some printers are capable of somewhat finer value quantization, but the quantizations of which even those are capable are almost always coarser than that of the original image. To achieve the illusion of finer gray-scale quantization, printers use half-toning, in which the gray level is achieved in a uniform-gray-level region by alternating black pixels with white pixels, the percentage of each depending on the gray-scale effect to be achieved. Of course, most images of interest have regions whose pixel values are not uniform, so there has to be a way to half-tone pixels whose intensity values change from one pixel to the next. A relatively fast way to perform half-toning on such images is known as "dithering."
Dithering involves comparing pixel values with respective threshold values of a dither matrix. To make the description more concrete, let us assume that the dither-matrix size is 128.times.128. Dashed lines in FIG. 1 divide a paper sheet's image-receiving region 10 into corresponding-size subregions. That is, subregion 11 is 128 pixel widths wide and 128 pixel heights high. A dithering process involves conceptually laying the dither matrix over each such subregion so that each pixel is associated with a respective dither threshold. Comparing a given pixel's image value with its thus-assigned threshold value determines whether the pixel will receive an ink dot. If the image value at a given pixel exceeds that pixel's dither threshold, then the pixel receives an ink dot. Otherwise it does not. So the dither-operation output for each pixel is a binary indication of whether that pixel will receive an ink dot.
The design of the dither-matrix threshold pattern depends on a number of factors. If the intended image-presentation system is of the type that does not effectively present isolated pixels, for instance, the dither-matrix pattern will typically be of the "clustered-dot," or "amplitude-modulation" variety, in which low threshold values tend to be clustered together so that printed pixels will tend not to be isolated. The resultant clusters of printed pixels are larger or smaller in accordance with the image's intended darkness. But a different type of dither-matrix pattern, known as the "dispersed-dot," or "frequency-modulation" type, is more frequently used when the image-presentation system can effectively print isolated pixels, because the results achievable with dispersed-dot matrices are generally considered superior.
Although dispersed-dot matrices' results can be superior, whether they actually are depends on the particular dither matrix's threshold-value pattern. Uniform gray areas in the resultant presented image tend to have annoying low-frequency patterns if high and low threshold values are not dispersed homogeneously throughout the dither matrix. But a fairly large dither matrix is required if such homogeneity is to be achieved without a loss of gray-scale resolution, and assigning threshold values with the required homogeneity to large dither matrices is not trivial. So considerable effort has been devoted to developing automatic ways of assigning threshold values.
U.S. Pat. No. 5,557,709 to Shu et al. for a Method and Apparatus for Dither Array Generation to Reduce Artifacts in Halftoned Images describes an advantageous approach. Whereas the purpose of the dither matrix is to yield homogeneously dispersed dots for any gray level, the method described in that patent begins with a particular, although somewhat arbitrarily chosen, initial gray level and chooses a homogeneous initial dot pattern in which the percentage of dots corresponds to the initial gray level. Individual dots are then removed one by one to achieve progressively lighter gray-scale values. (Of course, this is all done mathematically. The "dot pattern" is a binary-valued matrix having as many locations as the dither matrix to be generated, "adding a dot" at a particular pixel means setting the corresponding binary-matrix location's contents to a logical "1," and "removing a dot" means setting the location's contents to a logical "0.")
Now, if the dither matrix is to yield the selected initial dot pattern in response to the chosen initial gray level, all of its thresholds corresponding to the dot-containing locations in the initial pattern must have thresholds lower than that initial gray level. And when enough dots have been removed to result in the next-lighter gray level that pixel values of the intended resolution can represent, we know that threshold values corresponding to the remaining dots must be lower than one less than the initial gray level. Therefore, the threshold values corresponding to the locations from which dots were removed in achieving the next-lighter gray level must be equal to that gray level, and this is the threshold assigned to those dither-matrix locations. By continuing the process, lower thresholds can be assigned until all dither-matrix locations corresponding to dots in the initial pattern have been assigned thresholds. Higher threshold values are then assigned by again starting with that same initial dot pattern but adding dots rather than removing them.
The image quality that result from applying the resultant dither matrix depends on the initial dot pattern and on the manner in which dots are chosen for removal and addition. One advantageous way of choosing the initial dot pattern is described in the above-mentioned Shu et al. patent, which we hereby incorporate by reference. Briefly, it involves employing a further homogenization process to the dot pattern that results from applying the initial gray level to a different half-toning process, known as "error diffusion," which itself is known to result in relatively homogeneous dot patterns but is comparatively after dot removal or addition, dots are selected for removal by identifying the dot that is most crowded by other dots. This is also referred to as removing dots from the tightest "clusters." Dots are selected for addition--i.e., pixels without dots are selected to receive them--by identifying the pixels at the centers of the largest "voids." (Actually, the terms cluster and void are defined in most discussions not, as we have here, by reference to dots and their absence but rather by reference to the presence or absence of "minority" pixels. So when the number of dot-containing pixels overtakes the number of pixels without dots in those discussions, the process of placing dots in the lightest areas is no longer called placing them in the largest voids and instead starts being called adding them to the tightest "clusters"--in this case, clusters of pixels that do not contain dots.)